package leetcode.LinkedList;

/**
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 * <p>
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * <p>
 * 示例 1:
 * <p>
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 * <p>
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 *
 * @author MaoLin Wang
 * @date 2020/2/1112:07
 */
public class _143ReorderList {
    public static void reorderList(ListNode head) {
        if (head==null||head.next==null){
            return;
        }
        int length = ListNode.getLength(head);
        int mid = length / 2;

        //后半个链表
        ListNode last = head;
        //前半个链表
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;

        for (int i = 0; i < mid; i++) {
            last = last.next;
            temp = temp.next;
        }
        //切断前半段链表的next
        temp.next = null;

        //后半个链表反转
        last = _206ReverseList.reverseList2(last);
        //此时temp为前半个链表
        temp = pre.next;
        //前半个链表的后驱节点引用
        ListNode preLast = temp.next;
        while (last != null && temp != null) {
            temp.next = last;
            last = last.next;

            if (preLast != null) {
                temp.next.next = preLast;
                preLast = preLast.next;
            }else if (last!=null){
                temp.next.next=last;
                last=last.next;
            }
            temp = temp.next.next;
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        reorderList(l1);
    }
}
